Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent

摘要

We show that Delaunay triangulations and compressed quadtrees are equivalentstructures. More precisely, we give two algorithms: the first computes acompressed quadtree for a planar point set, given the Delaunay triangulation;the second finds the Delaunay triangulation, given a compressed quadtree. Bothalgorithms run in deterministic linear time on a pointer machine. Our workbuilds on and extends previous results by Krznaric and Levcopolous and Buchinand Mulzer. Our main tool for the second algorithm is the well-separated pairdecomposition(WSPD), a structure that has been used previously to findEuclidean minimum spanning trees in higher dimensions (Eppstein). We show thatknowing the WSPD (and a quadtree) suffices to compute a planar Euclideanminimum spanning tree (EMST) in linear time. With the EMST at hand, we can findthe Delaunay triangulation in linear time. As a corollary, we obtain deterministic versions of many previous algorithmsrelated to Delaunay triangulations, such as splitting planar Delaunaytriangulations, preprocessing imprecise points for faster Delaunay computation,and transdichotomous Delaunay triangulations.